//通过二叉树的前序遍历结果和中序遍历结果重建二叉树
#include <iostream>


struct BinaryTreeNode
{
	int		        m_nValue;
	BinaryTreeNode*	m_pLeft;
	BinaryTreeNode* m_pRight;
};

BinaryTreeNode* constructBinaryTree(int* preOrder,int* inOrder,int length)
{
	if(preOrder==NULL || inOrder==NULL || length<=0)
		return NULL;

	int rootValue = preOrder[0];
	BinaryTreeNode* pRoot = new BinaryTreeNode;
	pRoot->m_nValue = rootValue;

	//Left child tree
	int m_middle = 0;
	int* tempInOrder = inOrder;
	while(rootValue != inOrder[m_middle])
	{
		++tempInOrder;
		++m_middle;
	}

	int* leftPreOrder = preOrder+1;
	int* leftInOrder = inOrder;
	int leftLength = m_middle;
	BinaryTreeNode* leftChildTree = constructBinaryTree(leftPreOrder,leftInOrder,leftLength);
	//Right child tree
	int* rightPreOrder = preOrder+1+m_middle;
	int* rightInOrder = inOrder+1+m_middle;
	int rightLength = length - m_middle -1;
	BinaryTreeNode* rightChildTree = constructBinaryTree(rightPreOrder,rightInOrder,rightLength);

	//Construct 
	pRoot->m_pLeft = leftChildTree;
	pRoot->m_pRight = rightChildTree;

	return pRoot;
}

//
void preOrderBinaryTree(BinaryTreeNode* pNode)
{
	if(pNode==NULL)
		return;

	std::cout<<pNode->m_nValue<<" ";
	preOrderBinaryTree(pNode->m_pLeft);
	preOrderBinaryTree(pNode->m_pRight);

}

void inOrderBinaryTree(BinaryTreeNode* pNode)
{
	if(pNode==NULL)
		return ;

	inOrderBinaryTree(pNode->m_pLeft);
	std::cout<<pNode->m_nValue<<" ";
	inOrderBinaryTree(pNode->m_pRight);
}

int main()
{
	//int preOrder[] = {1,2,4,7,3,5,6,8};
	//int inOrder[] = {4,7,2,1,5,3,8,6};

	//int* preOrder = NULL;
	//int* inOrder = NULL;

	int preOrder[] = {1,2,4,7,3,5,6,8};
	int inOrder[] = {1,2,4,7,3,5,6,8};

	BinaryTreeNode* pRootNode = constructBinaryTree(preOrder,inOrder,8);
	std::cout<<"前序遍历结果：";
	preOrderBinaryTree(pRootNode);
	std::cout<<std::endl;
	std::cout<<"中序遍历结果：";
	inOrderBinaryTree(pRootNode);
	std::cout<<std::endl;
	return 0;
}